from collections import deque
from typing import *
from math import inf


class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        n = len(prices)
        f = [inf] * (n + 1)
        f[n] = 0
        for i in range(n - 1, -1, -1):
            v = prices[i]
            for j in range(i + 1, min(i + i + 3, n + 1)):
                f[i] = min(f[i], f[j] + v)
        return f[0]


class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        n = len(prices)
        q = deque([(n + 1, 0)])  # 哨兵
        for i in range(n, 0, -1):
            while q[-1][0] > i * 2 + 1:  # 右边离开窗口
                q.pop()
            f = prices[i - 1] + q[-1][1]
            while f <= q[0][1]:
                q.popleft()
            q.appendleft((i, f))  # 左边进入窗口
        return q[0][1]
